# 将 x 减到 0 的最小操作数: https://leetcode-cn.com/problems/minimum-operations-to-reduce-x-to-zero/


# 第一想法， 抽象为二叉树， 穷举超时
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        """
            感觉可以抽象乘一颗树形结构， 每次不是移动左边的， 就是移动右边的。都有两种选择。
            是个二叉树结构。
            从所有的可能结果中（累加等于 x）， 选出操作数最少的

            但是从数据规模上，这种方法不可取，超时
        """
        # 双指针，指向两边. total 记录当前总和， cntOp 记录操作数
        rst = len(nums) + 1
        def getMinOP(nums, i, j, total, cntOp):
            nonlocal rst
            # 终止条件
            if i > j or total > x:
                return
            
            if total == x:
                rst = min(cntOp, rst)
            
            if i + 1 < len(nums):
                getMinOP(nums, i + 1, j, total + nums[i + 1], cntOp + 1)
            if j - 1 >= 0:
                getMinOP(nums, i, j - 1, total + nums[j - 1], cntOp + 1)


        getMinOP(nums, -1, len(nums), 0, 0)
        return rst if rst != len(nums) + 1 else -1


